Seam Carving 是我在 Computational Thinking 時學到的演算法，可以針對圖片的內容做縮放。一般將圖片渲染到網頁上時，如果大小不符合容器高、寬，我們會採取一些做法：
Seam Carving 這個演算法可以在改變圖片比例的情況下做到裁剪，其原理是每次縮放時都找出圖片當中最不重要的部分並刪除，然後將圖片縫合起來。今天我們就來談談這個演算法吧！
我們來看看這張圖片
如果我們將他的比例改成這樣
可以發現圖片的內容整個都變形，非常不好看。
Seam Carving 這個演算法可以做到大致保持圖片內容，又可以不按照比例縮放。實際上是怎麼做到的呢？今天就來介紹一下這個演算法。
Seam Carving 的核心原理是找出圖片中最不重要部分刪除後，把剩下的部分「縫合」起來。那麼重點來了，要怎麼找到圖片中「不重要」的部分？又是怎麼定義不重要的呢？
我們先來看看這張圖片
再來看看這張圖片
這張圖片最重要的地方是黑白的交界點，只要能夠維持這個邊界，就算稍微修改比例，也不會感受到太大的差異。用肉眼看是看得懂，那麼在電腦視覺當中要怎麼找到這些點呢？
Sobel 包含兩個 3x3 的矩陣：
如果將圖片當作一個矩陣，將圖片的像素與矩陣相乘並求算梯度值，等於對影像做卷積（Convolution）。Sobel 透過計算離散差分，可以算出圖像亮度的梯度值。
從矩陣來看可能不好理解，但如果用程式碼來表示的話應該會清楚很多：
// 程式碼參考 https://github.com/miguelmota/sobel/blob/master/sobel.js
function Sobel(imageData) {
var width = imageData.width;
var height = imageData.height;
var kernelX = [
[-1, 0, 1],
[-2, 0, 2],
[-1, 0, 1],
];
var kernelY = [
[-1, -2, -1],
[0, 0, 0],
[1, 2, 1],
];
var sobelData = [];
var grayscaleData = [];
function bindPixelAt(data) {
return function (x, y, i) {
i = i || 0;
return data[(width * y + x) * 4 + i];
};
}
var data = imageData.data;
var pixelAt = bindPixelAt(data);
var x, y;
for (y = 0; y < height; y++) {
for (x = 0; x < width; x++) {
var r = pixelAt(x, y, 0);
var g = pixelAt(x, y, 1);
var b = pixelAt(x, y, 2);
var avg = (r + g + b) / 3;
grayscaleData.push(avg, avg, avg, 255);
}
}
pixelAt = bindPixelAt(grayscaleData);
for (y = 0; y < height; y++) {
for (x = 0; x < width; x++) {
var pixelX =
kernelX[0][0] * pixelAt(x - 1, y - 1) +
kernelX[0][1] * pixelAt(x, y - 1) +
kernelX[0][2] * pixelAt(x + 1, y - 1) +
kernelX[1][0] * pixelAt(x - 1, y) +
kernelX[1][1] * pixelAt(x, y) +
kernelX[1][2] * pixelAt(x + 1, y) +
kernelX[2][0] * pixelAt(x - 1, y + 1) +
kernelX[2][1] * pixelAt(x, y + 1) +
kernelX[2][2] * pixelAt(x + 1, y + 1);
var pixelY =
kernelY[0][0] * pixelAt(x - 1, y - 1) +
kernelY[0][1] * pixelAt(x, y - 1) +
kernelY[0][2] * pixelAt(x + 1, y - 1) +
kernelY[1][0] * pixelAt(x - 1, y) +
kernelY[1][1] * pixelAt(x, y) +
kernelY[1][2] * pixelAt(x + 1, y) +
kernelY[2][0] * pixelAt(x - 1, y + 1) +
kernelY[2][1] * pixelAt(x, y + 1) +
kernelY[2][2] * pixelAt(x + 1, y + 1);
var magnitude = Math.sqrt(pixelX * pixelX + pixelY * pixelY);
sobelData.push(magnitude, magnitude, magnitude, 255);
}
}
var clampedArray = sobelData;
return clampedArray;
}
從程式碼來看，Sobel 邊緣檢測實際在做的事是先將圖片轉為灰階後，再算出每個像素與相鄰像素的梯度值。
接下來我們把經過 Sobel 的圖片放到 canvas，這是原圖：
經過 Sobel 邊緣檢測後：
經過處理後的圖，可以發現交界處的部分（亮度變化大）的地方，值會越接近白色（也就是越靠近 255）。而亮度變化不明顯的地方則是呈黑色（靠近 0）
由於邊緣是圖片中比較重要的部分（越白的地方越重要），因此我們可以由上往下從相鄰像素當中找出最小值，然後把它從圖片移除就可以了。
然而，如果我們直接從上往下去找（Greedy），他可能不是全域最小值，例如：
如果從 0.7 開始找，可以得到 0.7+0.05+1.5=2.25。但如果從 0.8 開始找，則會得到 0.8+0.1+0.1=1.0。我們把經由 sobel 處理過的矩陣資料叫做 energy。我們可以先針對此 energy 作預處理。
先從最底部開始，由於每次都是從最小值裡選，所以可以確定當前的最小值就是全域最小值，這樣就可以用動態規劃來撰寫。首先先將原本的 energy 最底部複製過去，由下往上，開始計算相鄰元素的最小值，並加上自身的值：
這樣子就可以直接從 1.0 開始找，依序是 0.2、0.1，由於已經經過預處理，可以保證這條路線是總 energy 最少的。
接下來就是將對應座標記錄起來，以上述的例子來說可以得到：
[[1, 0], [0, 1], [0, 2]]
最後再將對應的像素刪除後即可，用 JavaScript 實作如下：
function buildEnergyMap(data, width, height) {
const energy = new Float32Array(width * height);
const getIndex = (x, y) => (y * width + x) * 4;
const getXY = (x, y) => y * width + x;
// bottom
// build bottom array
for (let x = width - 1; x >= 0; x--) {
const y = height - 1;
energy[y * width + x] = data[getIndex(x, y)];
}
for (let y = height - 2; y >= 0; y--) {
for (let x = 0; x < width; x++) {
const left = Math.max(0, x - 1);
const right = Math.min(x + 1, width - 1);
const minEnergy = Math.min(
energy[getXY(left, y + 1)],
energy[getXY(x, y + 1)],
energy[getXY(right, y + 1)]
);
energy[getXY(x, y)] += minEnergy;
energy[getXY(x, y)] += data[getIndex(x, y)] / 255;
}
}
return energy;
}
function seamCarving(canvas) {
const ctx = canvas.getContext("2d");
const imgData = ctx.getImageData(0, 0, canvas.width, canvas.height);
const { width, height, data } = imgData;
// Find the seam with minimum energy using dynamic programming
const energyMap = buildEnergyMap(data, canvas.width, canvas.height);
const seam = findSeam(energyMap, canvas.width, canvas.height);
for (let y = 0; y < height; y++) {
const seamIndex = seam[y][0];
for (let x = seamIndex; x < width - 1; x++) {
const offset = (y * width + x) * 4;
const nextOffset = (y * width + (x + 1)) * 4;
data[offset] = data[nextOffset];
data[offset + 1] = data[nextOffset + 1];
data[offset + 2] = data[nextOffset + 2];
data[offset + 3] = data[nextOffset + 3];
data[nextOffset] = 255;
data[nextOffset + 1] = 255;
data[nextOffset + 2] = 255;
data[nextOffset + 3] = 255;
}
}
ctx.clearRect(0, 0, canvas.width, canvas.height);
ctx.putImageData(imgData, 0, 0);
}
function findSeam(energyMap, width, height, startPoint) {
const getIndex = (x, y) => y * width + x;
let min = Number.MAX_VALUE;
let idx;
for (let x = 0; x < width; x++) {
if (min > energyMap[x]) {
min = energyMap[x];
idx = x;
}
}
const seam = [];
seam.push([idx, 0]);
let x = idx;
if (startPoint) {
x = startPoint;
}
for (let y = 0; y < height - 1; y++) {
let min = Number.MAX_VALUE;
const left = Math.max(0, x - 1);
const right = Math.min(x + 1, width - 1);
const leftValue = energyMap[getIndex(left, y + 1)];
const centerValue = energyMap[getIndex(x, y + 1)];
const rightValue = energyMap[getIndex(right, y + 1)];
const pairs = [
[left, leftValue],
[x, centerValue],
[right, rightValue],
];
let minX;
for (let i = 0; i < pairs.length; i++) {
min = Math.min(pairs[i][1], min);
}
const target = pairs.find((pair) => pair[1] === min);
seam.push([target[0], y + 1]);
x = target[0];
}
return seam;
}
Demo 的連結在此 。
雖然我們說可以讓圖片不成比例縮放，但根據圖片內容，還是會看起來怪怪的，尤其是當圖片的重要訊息被移除後會越來越奇怪。儘管如此我還是覺得它是個很有趣的演算法。
移除不重要的部分，這個中心思想其實在很多地方都看得到，例如聲音採樣，人耳聽不到的高頻可以移除掉節省空間；矩陣太複雜了，透過 SVD 奇異值轉換用重要的特徵向量來表示。雖然看似互不關聯，但觀念相通。
直接對圖片的每個像素做操作，而且又是用這種迴圈的方式來寫，在圖片尺寸比較大的時候會有非常顯著的 Delay。這時候可以考量一些優化，像是將對圖片的操作交給 GPU 處理，這部分可以用 WebGPU 或是 WebGL 達成，或是將計算挪給 Worker。
在實際使用上，雖然效果不錯，但其實還是要看圖片的內容為何，如果圖片的細節都很重要，都有非常明顯的亮度變化，那麼就算用 Seam Carving 也還是會失真很多。
本篇很多概念是從 Computational Thinking – Seam Carving 這部影片而來，解說是 3Brown1Blue 的作者 Grant Sanderson！裡頭有大量的視覺話解說，非常好理解。
iThome鐵人賽
看影片追技術